Question
In this paper, we will search for unusual clusters of complementary palindromes. The overarching research question is: “How do we find clusters of palindromes? How do we determine whether a cluster is just a chance occurrence or a potential replication site? Based on our analysis, we will then provide recommendations to biologists who are about to start experimentally searching for the origin of replication.
Setup
locations <- read.table('hcmv-25kgjn1-1rfrtkc.txt', header=TRUE)$location # Original
health <- read.csv('RAW_DATA-2iwcznn-2kr2xw0.csv', header = TRUE) # Additional
N <- 229354 # Base pairs
n <- 296 # Palindromes
Scenario 1: Random Scatter
To begin, pursue the point of view that structure in the data is indicated by departures from a uniform scatter of palindromes across the DNA.
Of course, a random uniform scatter does that mean that palindromes will be equally spaced as milestones on a freeway. There will be some gaps on the DNA where no palindromes occur, and there will be some clumping together of palindromes.
To look for structure examine the locations of the palindromes, the spacing between palindromes, and the counts of palindromes in non overlapping regions of the DNA. One starting place might be to see first how random scatter looks by using a computer to simulate it.
A computer can simulate 296 palindrome sites chosen at random along a DNA sequence of 229,354 bases using a pseudo random number generator. When this is done several times, by making seller sets of simulated palindrome locations, then the real data can be compared to the simulated data.
set.seed(0)
color <- 'red'
# Generate 3 samples from the uniform distribution with the same size and bounds as our data.
samples = list(sort(runif(n, min=0, max=N)), sort(runif(n, min=0, max=N)), sort(runif(n, min=0, max=N)))
# Dot plot of locations of palindromes in original data and uniform scatter.
title1 <- 'Locations of Palindromes'
title2 <- c(title1,'(Simulated)')
x.axis <- 'Base Pair'
symbol <- 3
stripchart(locations, pch=symbol, col=color, main=title1, xlab=x.axis)

for (sample in samples) {
stripchart(sample, pch=symbol, main=title2, xlab=x.axis)
}



# Additional dot plot of locations of palindromes in original data and uniform scatter.
dotchart(locations, color=color, main=title1, xlab=x.axis)

for (sample in samples) {
dotchart(sample, main=title2, xlab=x.axis)
}



# Histogram of locations of palindromes in original data and uniform scatter.
bins <- 35
hist(locations, col=color, breaks=bins, main=title1, xlab=x.axis)

for (sample in samples) {
hist(sample, breaks=bins, main=title2, xlab=x.axis)
}



# Scatterplot of spacing between consecutive palindromes
title1 <- 'Spacing between Consecutive Palindromes'
title2 <- c(title1,'(Simulated)')
x.axis <- 'Base Pair Location'
y.axis <- 'Distance (Base Pairs) from Previous Palindrome'
y.range <- c(0,5000)
plot(locations[-1], diff(locations), col=color, ylim=y.range, main=title1, xlab=x.axis, ylab=y.axis)

for (sample in samples) {
plot(sample[-1], diff(sample), ylim=y.range, main=title2, xlab=x.axis, ylab=y.axis)
}



# Histogram of counts of palindromes in non-overlapping regions in original data and uniform scatter.
interval.length <- 2500
title1 <- paste('Number of Palindromes in Non-Overlapping Regions of Length', interval.length)
title2 <- c(title1,'(Simulated)')
x.axis <- 'Number of Palindromes'
bins <- seq(0,20,1)
hist(as.vector(table(cut(locations, breaks=seq(0,N,interval.length), include.lowest = TRUE))), breaks=bins, col=color, main=title1, xlab=x.axis)

for (sample in samples) {
hist(as.vector(table(cut(sample, breaks=seq(0,N,interval.length), include.lowest = TRUE))), breaks=bins, main=title2, xlab=x.axis)
}



Scenario 2: Locations and Spacings
Use graphical methods to examine the spacings between consecutive palindromes and sum of consecutive pairs, triplets, etc, spacings. Compare what you find to what you would expect to find in a random scatter. Also, use graphical methods to compare locations of the palindromes.
Locations We performed the tests three times over three different lengths of sub-intervals.
# Histogram of locations of palindromes in original data and uniform scatter
uniform <- sample.int(N, size = n)
hist(locations, breaks = 20, probability = TRUE, col = rgb(1,0,0,0.5), main = "Location Data Distribution Comparison", xlab= "Palindrome Locations")
lines(density(locations, adjust = 2), col = 2)
hist(uniform,breaks = 20, probability = TRUE, col = rgb(0,0,1,0.5), add = TRUE)
lines(density(uniform, adjust = 2), col = 4)
legend(x = 180000, y = 0.000008, legend = c("Sample", "Uniform"), lty = c(1,1), col = c(rgb(1,0,0,0.5), rgb(0,0,1,0.5)))

# Chi-square Goodness of Fit Test
# Case 1: k(number of sub-intervals) = 50
k <- 50
locations.expected <- n/k
tab <- table(cut(locations, breaks = seq(0, N, length.out = k+1), include.lowest = TRUE))
locations.observed <- as.vector(tab)
chi_2 <- sum((locations.observed - locations.expected)^2/locations.expected)
chi2_compare <- qchisq(p = 0.95, df = 49)
p_value <- pchisq(chi_2, df = 49, lower.tail = FALSE)
print(cat("\nWhen conducting chi_square Goodness of fit test comparing locations(divided in 50 sub-intervals) against uniform distribution\n"))
When conducting chi_square Goodness of fit test comparing locations(divided in 50 sub-intervals) against uniform distribution
NULL
print(paste("The value of chi_square statistic is", chi_2))
[1] "The value of chi_square statistic is 66.5"
print(paste("The p_value is", p_value))
[1] "The p_value is 0.0486405818810276"
## Visualization of the Residual
Residuals <- (locations.observed - locations.expected) / sqrt(locations.expected)
plot(Residuals, type = 'h', ylab = "Standardized Residuals", xlab = "Palindrome locations", main = "Plot of Standardized Residual for Locations (divided in 50 sub-intervals)")

# Case 2: k(number of sub-intervals) = 100
k <- 100
locations.expected <- n/k
tab <- table(cut(locations, breaks = seq(0, N, length.out = k+1), include.lowest = TRUE))
locations.observed <- as.vector(tab)
chi_2 <- sum((locations.observed - locations.expected)^2/locations.expected)
chi2_compare <- qchisq(p = 0.95, df = 99)
p_value <- pchisq(chi_2, df = 99, lower.tail = FALSE)
print(cat("\nWhen conducting chi_square Goodness of fit test comparing locations(divided in 100 sub-intervals) against uniform distribution\n"))
When conducting chi_square Goodness of fit test comparing locations(divided in 100 sub-intervals) against uniform distribution
NULL
print(paste("The value of chi_square statistic is", chi_2))
[1] "The value of chi_square statistic is 141.162162162162"
print(paste("The p_value is", p_value))
[1] "The p_value is 0.00347914715199254"
## Visualization of the Residual
Residuals <- (locations.observed - locations.expected) / sqrt(locations.expected)
plot(Residuals, type = 'h', ylab = "Standardized Residuals", xlab = "Palindrome locations", main = "Plot of Standardized Residual for Locations (divided in 100 sub-intervals)")

# Case 3: k(number of sub-intervals) = 500
k <- 500
locations.expected <- n/k
tab <- table(cut(locations, breaks = seq(0, N, length.out = k+1), include.lowest = TRUE))
locations.observed <- as.vector(tab)
chi_2 <- sum((locations.observed - locations.expected)^2/locations.expected)
chi2_compare <- qchisq(p = 0.95, df = 499)
p_value <- pchisq(chi_2, df = 499, lower.tail = FALSE)
print(cat("\nWhen conducting chi_square Goodness of fit test comparing locations(divided in 500 sub-intervals) against uniform distribution\n"))
When conducting chi_square Goodness of fit test comparing locations(divided in 500 sub-intervals) against uniform distribution
NULL
print(paste("The value of chi_square statistic is", chi_2))
[1] "The value of chi_square statistic is 633.054054054054"
print(paste("The p_value is", p_value))
[1] "The p_value is 4.17057717528246e-05"
## Visualization of the Residual
Residuals <- (locations.observed - locations.expected) / sqrt(locations.expected)
plot(Residuals, type = 'h', ylab = "Standardized Residuals", xlab = "Palindrome locations", main = "Plot of Standardized Residual for Locations (divided in 500 sub-intervals)")

Inference: Null Hypothesis: Locations are distributed uniformly. Conclusion: Since p-value of this chi-square test is smaller than 0.05, we fail to reject the null hypothesis. It indicates that deviations as large as ours are not so likely. Hence, we conclude that it appears that uniform is not a reasonable initial model. Residual Conclusion: Since the value of the standardized residual is larger than 3, the probability model of a uniform distribution is lack of fit.
Spacings We performed the tests three times over three different lengths of sub-intervals.
# Consecutive Pairs
locations.sorted = sort(locations, decreasing = FALSE)
distance.pair <- abs(locations.sorted[-1]-locations.sorted[-length(locations.sorted)])
# Histogram of spacings of palindromes in original data and exponential distribution
hist(distance.pair, breaks= 15, col = rgb(1,0,0,0.5), probability = TRUE, main = "Consecutive Pairs Spacings Distribution Comparison", xlab = "Distance between Consecutive Palindromes Locations", ylim = c(0,0.001))
lines(density(distance.pair, adjust = 2), col = rgb(1,0,0,0.5))
Expo <- rexp(n-1, rate = 1/mean(distance.pair))
hist(Expo, breaks = 15, col = rgb(0,0,1,0.5), probability = TRUE, add = TRUE)
lines(density(Expo, adjust = 2), col = rgb(0,0,1,0.5))
legend(x = 4200, y = 0.0009, legend = c("Sample", "Exponential"), lty = c(1,1), col = c(rgb(1,0,0,0.5), rgb(0,0,1,0.5)))

# Chi-square Goodness of Fit Test
# Construct observed numbers of intervals
spacings.observed <- sort(distance.pair, decreasing = FALSE)
# Construct expected number of intervals
lambda <- 1/mean(distance.pair)
spacings.expected <- rep((n-1)*exp(-lambda),times = n-1)
chi_2 <- sum((spacings.observed - spacings.expected)^2/spacings.expected)
chi2_compare <- qchisq(p = 0.95, df = n-3)
p_value <- pchisq(chi_2, df = n-3, lower.tail = FALSE)
p_value
[1] 0
## Visualization of the Residual
Residuals <- (spacings.observed - spacings.expected) / sqrt(spacings.expected)
plot(Residuals, type = 'h', ylab = "Standardized Residuals", xlab = "Palindrome locations", main = "Plot of Standardized Residual for Locations (divided in 500 sub-intervals)")

# Consecutive Triplets
distance.triplets <- abs(locations.sorted[-1][-1]-locations.sorted[-length(locations.sorted)][-length(locations.sorted)+1])
# Histogram of spacings of palindromes in original data and exponential distribution
hist(distance.triplets, breaks= 15, col = rgb(1,0,0,0.5), probability = TRUE, main = "Consecutive Triplets Spacings Distribution Comparison", xlab = "Distance between hits that are two aparatus", ylim = c(0,0.001))
lines(density(distance.pair, adjust = 2), col = rgb(1,0,0,0.5))
Gam <- rgamma(n-2, 2, 1/mean(distance.pair))
hist(Gam, breaks = 15, col = rgb(0,0,1,0.5), probability = TRUE, add = TRUE)
lines(density(Gam, adjust = 2), col = rgb(0,0,1,0.5))
legend(x = 4200, y = 0.0009, legend = c("Sample", "Gamma"), lty = c(1,1), col = c(rgb(1,0,0,0.5), rgb(0,0,1,0.5)))

Scenario 3: Counts
Use graphical methods and more formal statistical tests to examine the counts of palindromes in various regions of the DNA. Split the DNA into nonoverlapping regions of equal length to compare the number of palindomres in an interval to the number of that you would expect from uniform random scatter. The counts for shorter regions will be more variable than those for logner regions. Also, consider classifying the regions according to the number of counts.
k <- 50
tab <- table(cut(locations, breaks = seq(0, N, length.out = k+1), include.lowest = TRUE))
counts.obs <- as.vector(tab)
a <- table(cut(counts.obs, breaks = seq(min(counts.obs), max(counts.obs), length.out = k+1), include.lowest = TRUE))
# Histogram of counts of palindromes in original data and poisson distribution
hist(counts.obs, breaks = 15, col = rgb(1,0,0,0.5), probability = TRUE, main = "Counts Distribution Comparison (50 Sub-intervals)", xlab = "Number of Palindromes Sites Inside an Interval", ylim = c(0,0.2))
lines(density(counts.obs, adjust = 2), col = rgb(1,0,0,0.5))
Pois <- rpois(n, lambda = mean(counts.obs))
hist(Pois, breaks = 15, col = rgb(0,0,1,0.5), probability = TRUE, add = TRUE)
lines(density(Pois, adjust = 2), col = rgb(0,0,1,0.5))
legend(x = 12, y = 0.15, legend = c("sample", "Poisson"), lty = c(1,1), col = c(rgb(1,0,0,0.5), rgb(0,0,1,0.5)))

# Chi-Square Testing
# Construct palindrome count number
palindrome.count <- c("0,1,2", "3","4","5","6","7","8+")
# Construct observed number of intervals
intervals.observed <- c(8, 9, 13, 10, 8, 8, 5)
# Construct expected number of intervals
expected <- c()
lambda <- n/k
for (i in c(0:17)){
expect <- k* exp(-lambda)* lambda**i /factorial(i)
expected <- c(expected, expect)
}
sum <- 0
for (j in c(9:17)){
sum <- sum+expected[j]
}
intervals.expected <- c(expected[1]+expected[2]+expected[3],expected[4],expected[5],expected[6],expected[7],expected[8],sum)
# Create contingency table
b <- data.frame(palindrome.count,intervals.observed,intervals.expected)
b
chi_2 <- sum((intervals.observed - intervals.expected)^2/intervals.expected)
chi2_compare <- qchisq(p = 0.95, df = 7)
p_value <- pchisq(chi_2, df = 7, lower.tail = FALSE)
print(cat("\nWhen conducting chi_square Goodness of fit test comparing locations(divided in 500 sub-intervals) against uniform distribution\n"))
When conducting chi_square Goodness of fit test comparing locations(divided in 500 sub-intervals) against uniform distribution
NULL
print(paste("The value of chi_square statistic is", chi_2))
[1] "The value of chi_square statistic is 21.2720502400911"
print(paste("The p_value is", p_value))
[1] "The p_value is 0.00338769156571031"
Scenario 4: The Biggest Cluster
Does the interval with the greatest number of palindromes indicate a potential origin of replication? Be careful in making your intervals, for any small, but significant deviations from random scatter, such as a tight cluster of a few palindromes, could easily go undetected if the regions examined are too large. Also, if the regions are too small, a cluster of palindromes may be split between adjacent interavls and not appear as a high-count interval.
final <- array(dim=c(500,1))
interval_length <- array(dim=c(500,1))
lamda <- array(dim=c(500,1))
for (k in 50:500){
tab <- table(cut(locations, breaks = seq(0, N, length.out = k+1), include.lowest = TRUE))
head(tab,10)
tab<-as.vector(tab)
lamda[k,] <-sum(tab)/k
threshold <-max(tab)
result <- 0
interval_length[k,] <- N/k
for (i in 0:(threshold-1)){
result <- result+((lamda[k]^i)*exp(-lamda[k])/factorial(i))
}
final[k,] <- 1-result^k
}
result <- data.frame(lamda,interval_length,final)
# Display Table containing the probability of a Poisson Distribution having e greatest number of hits at least k for each sub-interval divisions
result[c(50,100,500),]
LS0tCnRpdGxlOiAiQ0FTRSBTVFVEWSAzOiBTRUFSQ0ggRk9SIFRIRSBVTlVTVUFMIENMVVNURVIgSU4gVEhFIFBBTElORFJPTUVTIgpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sKLS0tCgoKCiMjIFF1ZXN0aW9uCkluIHRoaXMgcGFwZXIsIHdlIHdpbGwgc2VhcmNoIGZvciB1bnVzdWFsIGNsdXN0ZXJzIG9mIGNvbXBsZW1lbnRhcnkgcGFsaW5kcm9tZXMuIFRoZSBvdmVyYXJjaGluZyByZXNlYXJjaCBxdWVzdGlvbiBpczog4oCcSG93IGRvIHdlIGZpbmQgY2x1c3RlcnMgb2YgcGFsaW5kcm9tZXM/IEhvdyBkbyB3ZSBkZXRlcm1pbmUgd2hldGhlciBhIGNsdXN0ZXIgaXMganVzdCBhIGNoYW5jZSBvY2N1cnJlbmNlIG9yIGEgcG90ZW50aWFsIHJlcGxpY2F0aW9uIHNpdGU/IEJhc2VkIG9uIG91ciBhbmFseXNpcywgd2Ugd2lsbCB0aGVuIHByb3ZpZGUgcmVjb21tZW5kYXRpb25zIHRvIGJpb2xvZ2lzdHMgd2hvIGFyZSBhYm91dCB0byBzdGFydCBleHBlcmltZW50YWxseSBzZWFyY2hpbmcgZm9yIHRoZSBvcmlnaW4gb2YgcmVwbGljYXRpb24uCgoKCiMjIFNldHVwCmBgYHtyfQpsb2NhdGlvbnMgPC0gcmVhZC50YWJsZSgnaGNtdi0yNWtnam4xLTFyZnJ0a2MudHh0JywgaGVhZGVyPVRSVUUpJGxvY2F0aW9uICAjIE9yaWdpbmFsCmhlYWx0aCA8LSByZWFkLmNzdignUkFXX0RBVEEtMml3Y3pubi0ya3IyeHcwLmNzdicsIGhlYWRlciA9IFRSVUUpICAjIEFkZGl0aW9uYWwKCk4gPC0gMjI5MzU0ICAjIEJhc2UgcGFpcnMKbiA8LSAyOTYgICMgUGFsaW5kcm9tZXMKYGBgCgoKCiMjIFNjZW5hcmlvIDE6IFJhbmRvbSBTY2F0dGVyClRvIGJlZ2luLCBwdXJzdWUgdGhlIHBvaW50IG9mIHZpZXcgdGhhdCBzdHJ1Y3R1cmUgaW4gdGhlIGRhdGEgaXMgaW5kaWNhdGVkIGJ5IGRlcGFydHVyZXMgZnJvbSBhIHVuaWZvcm0gc2NhdHRlciBvZiBwYWxpbmRyb21lcyBhY3Jvc3MgdGhlIEROQS4KCipPZiBjb3Vyc2UsIGEgcmFuZG9tIHVuaWZvcm0gc2NhdHRlciBkb2VzIHRoYXQgbWVhbiB0aGF0IHBhbGluZHJvbWVzIHdpbGwgYmUgZXF1YWxseSBzcGFjZWQgYXMgbWlsZXN0b25lcyBvbiBhIGZyZWV3YXkuIFRoZXJlIHdpbGwgYmUgc29tZSBnYXBzIG9uIHRoZSBETkEgd2hlcmUgbm8gcGFsaW5kcm9tZXMgb2NjdXIsIGFuZCB0aGVyZSB3aWxsIGJlIHNvbWUgY2x1bXBpbmcgdG9nZXRoZXIgb2YgcGFsaW5kcm9tZXMuKgoKVG8gbG9vayBmb3Igc3RydWN0dXJlIGV4YW1pbmUgdGhlIGxvY2F0aW9ucyBvZiB0aGUgcGFsaW5kcm9tZXMsIHRoZSBzcGFjaW5nIGJldHdlZW4gcGFsaW5kcm9tZXMsIGFuZCB0aGUgY291bnRzIG9mIHBhbGluZHJvbWVzIGluIG5vbiBvdmVybGFwcGluZyByZWdpb25zIG9mIHRoZSBETkEuIE9uZSBzdGFydGluZyBwbGFjZSBtaWdodCBiZSB0byBzZWUgZmlyc3QgaG93IHJhbmRvbSBzY2F0dGVyIGxvb2tzIGJ5IHVzaW5nIGEgY29tcHV0ZXIgdG8gc2ltdWxhdGUgaXQuCgoqQSBjb21wdXRlciBjYW4gc2ltdWxhdGUgMjk2IHBhbGluZHJvbWUgc2l0ZXMgY2hvc2VuIGF0IHJhbmRvbSBhbG9uZyBhIEROQSBzZXF1ZW5jZSBvZiAyMjksMzU0IGJhc2VzIHVzaW5nIGEgcHNldWRvIHJhbmRvbSBudW1iZXIgZ2VuZXJhdG9yLiBXaGVuIHRoaXMgaXMgZG9uZSBzZXZlcmFsIHRpbWVzLCBieSBtYWtpbmcgc2VsbGVyIHNldHMgb2Ygc2ltdWxhdGVkIHBhbGluZHJvbWUgbG9jYXRpb25zLCB0aGVuIHRoZSByZWFsIGRhdGEgY2FuIGJlIGNvbXBhcmVkIHRvIHRoZSBzaW11bGF0ZWQgZGF0YS4qCmBgYHtyfQpzZXQuc2VlZCgwKQpjb2xvciA8LSAncmVkJwoKIyBHZW5lcmF0ZSAzIHNhbXBsZXMgZnJvbSB0aGUgdW5pZm9ybSBkaXN0cmlidXRpb24gd2l0aCB0aGUgc2FtZSBzaXplIGFuZCBib3VuZHMgYXMgb3VyIGRhdGEuCnNhbXBsZXMgPSBsaXN0KHNvcnQocnVuaWYobiwgbWluPTAsIG1heD1OKSksIHNvcnQocnVuaWYobiwgbWluPTAsIG1heD1OKSksIHNvcnQocnVuaWYobiwgbWluPTAsIG1heD1OKSkpCgoKCiMgRG90IHBsb3Qgb2YgbG9jYXRpb25zIG9mIHBhbGluZHJvbWVzIGluIG9yaWdpbmFsIGRhdGEgYW5kIHVuaWZvcm0gc2NhdHRlci4KdGl0bGUxIDwtICdMb2NhdGlvbnMgb2YgUGFsaW5kcm9tZXMnCnRpdGxlMiA8LSBjKHRpdGxlMSwnKFNpbXVsYXRlZCknKQp4LmF4aXMgPC0gJ0Jhc2UgUGFpcicKc3ltYm9sIDwtIDMKc3RyaXBjaGFydChsb2NhdGlvbnMsIHBjaD1zeW1ib2wsIGNvbD1jb2xvciwgbWFpbj10aXRsZTEsIHhsYWI9eC5heGlzKQpmb3IgKHNhbXBsZSBpbiBzYW1wbGVzKSB7CiAgc3RyaXBjaGFydChzYW1wbGUsIHBjaD1zeW1ib2wsIG1haW49dGl0bGUyLCB4bGFiPXguYXhpcykKfQoKIyBBZGRpdGlvbmFsIGRvdCBwbG90IG9mIGxvY2F0aW9ucyBvZiBwYWxpbmRyb21lcyBpbiBvcmlnaW5hbCBkYXRhIGFuZCB1bmlmb3JtIHNjYXR0ZXIuCmRvdGNoYXJ0KGxvY2F0aW9ucywgY29sb3I9Y29sb3IsIG1haW49dGl0bGUxLCB4bGFiPXguYXhpcykKZm9yIChzYW1wbGUgaW4gc2FtcGxlcykgewogIGRvdGNoYXJ0KHNhbXBsZSwgbWFpbj10aXRsZTIsIHhsYWI9eC5heGlzKQp9CgojIEhpc3RvZ3JhbSBvZiBsb2NhdGlvbnMgb2YgcGFsaW5kcm9tZXMgaW4gb3JpZ2luYWwgZGF0YSBhbmQgdW5pZm9ybSBzY2F0dGVyLgpiaW5zIDwtIDM1Cmhpc3QobG9jYXRpb25zLCBjb2w9Y29sb3IsIGJyZWFrcz1iaW5zLCBtYWluPXRpdGxlMSwgeGxhYj14LmF4aXMpCmZvciAoc2FtcGxlIGluIHNhbXBsZXMpIHsKICBoaXN0KHNhbXBsZSwgYnJlYWtzPWJpbnMsIG1haW49dGl0bGUyLCB4bGFiPXguYXhpcykKfQoKCgojIFNjYXR0ZXJwbG90IG9mIHNwYWNpbmcgYmV0d2VlbiBjb25zZWN1dGl2ZSBwYWxpbmRyb21lcwp0aXRsZTEgPC0gJ1NwYWNpbmcgYmV0d2VlbiBDb25zZWN1dGl2ZSBQYWxpbmRyb21lcycKdGl0bGUyIDwtIGModGl0bGUxLCcoU2ltdWxhdGVkKScpCnguYXhpcyA8LSAnQmFzZSBQYWlyIExvY2F0aW9uJwp5LmF4aXMgPC0gJ0Rpc3RhbmNlIChCYXNlIFBhaXJzKSBmcm9tIFByZXZpb3VzIFBhbGluZHJvbWUnCnkucmFuZ2UgPC0gYygwLDUwMDApCnBsb3QobG9jYXRpb25zWy0xXSwgZGlmZihsb2NhdGlvbnMpLCBjb2w9Y29sb3IsIHlsaW09eS5yYW5nZSwgbWFpbj10aXRsZTEsIHhsYWI9eC5heGlzLCB5bGFiPXkuYXhpcykKZm9yIChzYW1wbGUgaW4gc2FtcGxlcykgewogIHBsb3Qoc2FtcGxlWy0xXSwgZGlmZihzYW1wbGUpLCB5bGltPXkucmFuZ2UsIG1haW49dGl0bGUyLCB4bGFiPXguYXhpcywgeWxhYj15LmF4aXMpCn0KCgoKIyBIaXN0b2dyYW0gb2YgY291bnRzIG9mIHBhbGluZHJvbWVzIGluIG5vbi1vdmVybGFwcGluZyByZWdpb25zIGluIG9yaWdpbmFsIGRhdGEgYW5kIHVuaWZvcm0gc2NhdHRlci4KaW50ZXJ2YWwubGVuZ3RoIDwtIDI1MDAKdGl0bGUxIDwtIHBhc3RlKCdOdW1iZXIgb2YgUGFsaW5kcm9tZXMgaW4gTm9uLU92ZXJsYXBwaW5nIFJlZ2lvbnMgb2YgTGVuZ3RoJywgaW50ZXJ2YWwubGVuZ3RoKQp0aXRsZTIgPC0gYyh0aXRsZTEsJyhTaW11bGF0ZWQpJykKeC5heGlzIDwtICdOdW1iZXIgb2YgUGFsaW5kcm9tZXMnCmJpbnMgPC0gc2VxKDAsMjAsMSkKaGlzdChhcy52ZWN0b3IodGFibGUoY3V0KGxvY2F0aW9ucywgYnJlYWtzPXNlcSgwLE4saW50ZXJ2YWwubGVuZ3RoKSwgaW5jbHVkZS5sb3dlc3QgPSBUUlVFKSkpLCBicmVha3M9YmlucywgY29sPWNvbG9yLCBtYWluPXRpdGxlMSwgeGxhYj14LmF4aXMpCmZvciAoc2FtcGxlIGluIHNhbXBsZXMpIHsKICBoaXN0KGFzLnZlY3Rvcih0YWJsZShjdXQoc2FtcGxlLCBicmVha3M9c2VxKDAsTixpbnRlcnZhbC5sZW5ndGgpLCBpbmNsdWRlLmxvd2VzdCA9IFRSVUUpKSksIGJyZWFrcz1iaW5zLCBtYWluPXRpdGxlMiwgeGxhYj14LmF4aXMpCn0KYGBgCgoKCiMjIFNjZW5hcmlvIDI6IExvY2F0aW9ucyBhbmQgU3BhY2luZ3MKVXNlIGdyYXBoaWNhbCBtZXRob2RzIHRvIGV4YW1pbmUgdGhlIHNwYWNpbmdzIGJldHdlZW4gY29uc2VjdXRpdmUgcGFsaW5kcm9tZXMgYW5kIHN1bSBvZiBjb25zZWN1dGl2ZSBwYWlycywgdHJpcGxldHMsIGV0Yywgc3BhY2luZ3MuIENvbXBhcmUgd2hhdCB5b3UgZmluZCB0byB3aGF0IHlvdSB3b3VsZCBleHBlY3QgdG8gZmluZCBpbiBhIHJhbmRvbSBzY2F0dGVyLiBBbHNvLCB1c2UgZ3JhcGhpY2FsIG1ldGhvZHMgdG8gY29tcGFyZSBsb2NhdGlvbnMgb2YgdGhlIHBhbGluZHJvbWVzLgoKTG9jYXRpb25zCldlIHBlcmZvcm1lZCB0aGUgdGVzdHMgdGhyZWUgdGltZXMgb3ZlciB0aHJlZSBkaWZmZXJlbnQgbGVuZ3RocyBvZiBzdWItaW50ZXJ2YWxzLgpgYGB7cn0KIyBIaXN0b2dyYW0gb2YgbG9jYXRpb25zIG9mIHBhbGluZHJvbWVzIGluIG9yaWdpbmFsIGRhdGEgYW5kIHVuaWZvcm0gc2NhdHRlcgp1bmlmb3JtIDwtIHNhbXBsZS5pbnQoTiwgc2l6ZSA9IG4pCmhpc3QobG9jYXRpb25zLCBicmVha3MgPSAyMCwgcHJvYmFiaWxpdHkgPSBUUlVFLCBjb2wgPSByZ2IoMSwwLDAsMC41KSwgbWFpbiA9ICJMb2NhdGlvbiBEYXRhIERpc3RyaWJ1dGlvbiBDb21wYXJpc29uIiwgeGxhYj0gIlBhbGluZHJvbWUgTG9jYXRpb25zIikKbGluZXMoZGVuc2l0eShsb2NhdGlvbnMsIGFkanVzdCA9IDIpLCBjb2wgPSAyKQpoaXN0KHVuaWZvcm0sYnJlYWtzID0gMjAsIHByb2JhYmlsaXR5ID0gVFJVRSwgY29sID0gcmdiKDAsMCwxLDAuNSksIGFkZCA9IFRSVUUpCmxpbmVzKGRlbnNpdHkodW5pZm9ybSwgYWRqdXN0ID0gMiksIGNvbCA9IDQpCmxlZ2VuZCh4ID0gMTgwMDAwLCB5ID0gMC4wMDAwMDgsIGxlZ2VuZCA9IGMoIlNhbXBsZSIsICJVbmlmb3JtIiksIGx0eSA9IGMoMSwxKSwgY29sID0gYyhyZ2IoMSwwLDAsMC41KSwgcmdiKDAsMCwxLDAuNSkpKQoKIyBDaGktc3F1YXJlIEdvb2RuZXNzIG9mIEZpdCBUZXN0CiMgQ2FzZSAxOiBrKG51bWJlciBvZiBzdWItaW50ZXJ2YWxzKSA9IDUwCmsgPC0gNTAKbG9jYXRpb25zLmV4cGVjdGVkIDwtIG4vawp0YWIgPC0gdGFibGUoY3V0KGxvY2F0aW9ucywgYnJlYWtzID0gc2VxKDAsIE4sIGxlbmd0aC5vdXQgPSBrKzEpLCBpbmNsdWRlLmxvd2VzdCA9IFRSVUUpKQpsb2NhdGlvbnMub2JzZXJ2ZWQgPC0gYXMudmVjdG9yKHRhYikKY2hpXzIgPC0gc3VtKChsb2NhdGlvbnMub2JzZXJ2ZWQgLSBsb2NhdGlvbnMuZXhwZWN0ZWQpXjIvbG9jYXRpb25zLmV4cGVjdGVkKQpjaGkyX2NvbXBhcmUgPC0gcWNoaXNxKHAgPSAwLjk1LCBkZiA9IDQ5KQpwX3ZhbHVlIDwtIHBjaGlzcShjaGlfMiwgZGYgPSA0OSwgbG93ZXIudGFpbCA9IEZBTFNFKQpwcmludChjYXQoIlxuV2hlbiBjb25kdWN0aW5nIGNoaV9zcXVhcmUgR29vZG5lc3Mgb2YgZml0IHRlc3QgY29tcGFyaW5nIGxvY2F0aW9ucyhkaXZpZGVkIGluIDUwIHN1Yi1pbnRlcnZhbHMpIGFnYWluc3QgdW5pZm9ybSBkaXN0cmlidXRpb25cbiIpKQpwcmludChwYXN0ZSgiVGhlIHZhbHVlIG9mIGNoaV9zcXVhcmUgc3RhdGlzdGljIGlzIiwgY2hpXzIpKQpwcmludChwYXN0ZSgiVGhlIHBfdmFsdWUgaXMiLCBwX3ZhbHVlKSkKCiMjIFZpc3VhbGl6YXRpb24gb2YgdGhlIFJlc2lkdWFsClJlc2lkdWFscyA8LSAobG9jYXRpb25zLm9ic2VydmVkIC0gbG9jYXRpb25zLmV4cGVjdGVkKSAvIHNxcnQobG9jYXRpb25zLmV4cGVjdGVkKQpwbG90KFJlc2lkdWFscywgdHlwZSA9ICdoJywgeWxhYiA9ICJTdGFuZGFyZGl6ZWQgUmVzaWR1YWxzIiwgeGxhYiA9ICJQYWxpbmRyb21lIGxvY2F0aW9ucyIsIG1haW4gPSAiUGxvdCBvZiBTdGFuZGFyZGl6ZWQgUmVzaWR1YWwgZm9yIExvY2F0aW9ucyAoZGl2aWRlZCBpbiA1MCBzdWItaW50ZXJ2YWxzKSIpCgojIENhc2UgMjogayhudW1iZXIgb2Ygc3ViLWludGVydmFscykgPSAxMDAKayA8LSAxMDAKbG9jYXRpb25zLmV4cGVjdGVkIDwtIG4vawp0YWIgPC0gdGFibGUoY3V0KGxvY2F0aW9ucywgYnJlYWtzID0gc2VxKDAsIE4sIGxlbmd0aC5vdXQgPSBrKzEpLCBpbmNsdWRlLmxvd2VzdCA9IFRSVUUpKQpsb2NhdGlvbnMub2JzZXJ2ZWQgPC0gYXMudmVjdG9yKHRhYikKY2hpXzIgPC0gc3VtKChsb2NhdGlvbnMub2JzZXJ2ZWQgLSBsb2NhdGlvbnMuZXhwZWN0ZWQpXjIvbG9jYXRpb25zLmV4cGVjdGVkKQpjaGkyX2NvbXBhcmUgPC0gcWNoaXNxKHAgPSAwLjk1LCBkZiA9IDk5KQpwX3ZhbHVlIDwtIHBjaGlzcShjaGlfMiwgZGYgPSA5OSwgbG93ZXIudGFpbCA9IEZBTFNFKQpwcmludChjYXQoIlxuV2hlbiBjb25kdWN0aW5nIGNoaV9zcXVhcmUgR29vZG5lc3Mgb2YgZml0IHRlc3QgY29tcGFyaW5nIGxvY2F0aW9ucyhkaXZpZGVkIGluIDEwMCBzdWItaW50ZXJ2YWxzKSBhZ2FpbnN0IHVuaWZvcm0gZGlzdHJpYnV0aW9uXG4iKSkKcHJpbnQocGFzdGUoIlRoZSB2YWx1ZSBvZiBjaGlfc3F1YXJlIHN0YXRpc3RpYyBpcyIsIGNoaV8yKSkKcHJpbnQocGFzdGUoIlRoZSBwX3ZhbHVlIGlzIiwgcF92YWx1ZSkpCgojIyBWaXN1YWxpemF0aW9uIG9mIHRoZSBSZXNpZHVhbApSZXNpZHVhbHMgPC0gKGxvY2F0aW9ucy5vYnNlcnZlZCAtIGxvY2F0aW9ucy5leHBlY3RlZCkgLyBzcXJ0KGxvY2F0aW9ucy5leHBlY3RlZCkKcGxvdChSZXNpZHVhbHMsIHR5cGUgPSAnaCcsIHlsYWIgPSAiU3RhbmRhcmRpemVkIFJlc2lkdWFscyIsIHhsYWIgPSAiUGFsaW5kcm9tZSBsb2NhdGlvbnMiLCBtYWluID0gIlBsb3Qgb2YgU3RhbmRhcmRpemVkIFJlc2lkdWFsIGZvciBMb2NhdGlvbnMgKGRpdmlkZWQgaW4gMTAwIHN1Yi1pbnRlcnZhbHMpIikKCiMgQ2FzZSAzOiBrKG51bWJlciBvZiBzdWItaW50ZXJ2YWxzKSA9IDUwMAprIDwtIDUwMApsb2NhdGlvbnMuZXhwZWN0ZWQgPC0gbi9rCnRhYiA8LSB0YWJsZShjdXQobG9jYXRpb25zLCBicmVha3MgPSBzZXEoMCwgTiwgbGVuZ3RoLm91dCA9IGsrMSksIGluY2x1ZGUubG93ZXN0ID0gVFJVRSkpCmxvY2F0aW9ucy5vYnNlcnZlZCA8LSBhcy52ZWN0b3IodGFiKQpjaGlfMiA8LSBzdW0oKGxvY2F0aW9ucy5vYnNlcnZlZCAtIGxvY2F0aW9ucy5leHBlY3RlZCleMi9sb2NhdGlvbnMuZXhwZWN0ZWQpCmNoaTJfY29tcGFyZSA8LSBxY2hpc3EocCA9IDAuOTUsIGRmID0gNDk5KQpwX3ZhbHVlIDwtIHBjaGlzcShjaGlfMiwgZGYgPSA0OTksIGxvd2VyLnRhaWwgPSBGQUxTRSkKcHJpbnQoY2F0KCJcbldoZW4gY29uZHVjdGluZyBjaGlfc3F1YXJlIEdvb2RuZXNzIG9mIGZpdCB0ZXN0IGNvbXBhcmluZyBsb2NhdGlvbnMoZGl2aWRlZCBpbiA1MDAgc3ViLWludGVydmFscykgYWdhaW5zdCB1bmlmb3JtIGRpc3RyaWJ1dGlvblxuIikpCnByaW50KHBhc3RlKCJUaGUgdmFsdWUgb2YgY2hpX3NxdWFyZSBzdGF0aXN0aWMgaXMiLCBjaGlfMikpCnByaW50KHBhc3RlKCJUaGUgcF92YWx1ZSBpcyIsIHBfdmFsdWUpKQoKIyMgVmlzdWFsaXphdGlvbiBvZiB0aGUgUmVzaWR1YWwKUmVzaWR1YWxzIDwtIChsb2NhdGlvbnMub2JzZXJ2ZWQgLSBsb2NhdGlvbnMuZXhwZWN0ZWQpIC8gc3FydChsb2NhdGlvbnMuZXhwZWN0ZWQpCnBsb3QoUmVzaWR1YWxzLCB0eXBlID0gJ2gnLCB5bGFiID0gIlN0YW5kYXJkaXplZCBSZXNpZHVhbHMiLCB4bGFiID0gIlBhbGluZHJvbWUgbG9jYXRpb25zIiwgbWFpbiA9ICJQbG90IG9mIFN0YW5kYXJkaXplZCBSZXNpZHVhbCBmb3IgTG9jYXRpb25zIChkaXZpZGVkIGluIDUwMCBzdWItaW50ZXJ2YWxzKSIpCmBgYApJbmZlcmVuY2U6Ck51bGwgSHlwb3RoZXNpczogTG9jYXRpb25zIGFyZSBkaXN0cmlidXRlZCB1bmlmb3JtbHkuCkNvbmNsdXNpb246IFNpbmNlIHAtdmFsdWUgb2YgdGhpcyBjaGktc3F1YXJlIHRlc3QgaXMgc21hbGxlciB0aGFuIDAuMDUsIHdlIGZhaWwgdG8gcmVqZWN0IHRoZSBudWxsIGh5cG90aGVzaXMuIEl0IGluZGljYXRlcyB0aGF0IGRldmlhdGlvbnMgYXMgbGFyZ2UgYXMgb3VycyBhcmUgbm90IHNvIGxpa2VseS4gSGVuY2UsIHdlIGNvbmNsdWRlIHRoYXQgaXQgYXBwZWFycyB0aGF0IHVuaWZvcm0gaXMgbm90IGEgcmVhc29uYWJsZSBpbml0aWFsIG1vZGVsLiAKUmVzaWR1YWwgQ29uY2x1c2lvbjoKU2luY2UgdGhlIHZhbHVlIG9mIHRoZSBzdGFuZGFyZGl6ZWQgcmVzaWR1YWwgaXMgbGFyZ2VyIHRoYW4gMywgdGhlIHByb2JhYmlsaXR5IG1vZGVsIG9mIGEgdW5pZm9ybSBkaXN0cmlidXRpb24gaXMgbGFjayBvZiBmaXQuCgpTcGFjaW5ncwpXZSBwZXJmb3JtZWQgdGhlIHRlc3RzIHRocmVlIHRpbWVzIG92ZXIgdGhyZWUgZGlmZmVyZW50IGxlbmd0aHMgb2Ygc3ViLWludGVydmFscy4KYGBge3J9CiMgQ29uc2VjdXRpdmUgUGFpcnMKbG9jYXRpb25zLnNvcnRlZCA9IHNvcnQobG9jYXRpb25zLCBkZWNyZWFzaW5nID0gRkFMU0UpCmRpc3RhbmNlLnBhaXIgPC0gYWJzKGxvY2F0aW9ucy5zb3J0ZWRbLTFdLWxvY2F0aW9ucy5zb3J0ZWRbLWxlbmd0aChsb2NhdGlvbnMuc29ydGVkKV0pCgojIEhpc3RvZ3JhbSBvZiBzcGFjaW5ncyBvZiBwYWxpbmRyb21lcyBpbiBvcmlnaW5hbCBkYXRhIGFuZCBleHBvbmVudGlhbCBkaXN0cmlidXRpb24KaGlzdChkaXN0YW5jZS5wYWlyLCBicmVha3M9IDE1LCBjb2wgPSByZ2IoMSwwLDAsMC41KSwgcHJvYmFiaWxpdHkgPSBUUlVFLCBtYWluID0gIkNvbnNlY3V0aXZlIFBhaXJzIFNwYWNpbmdzIERpc3RyaWJ1dGlvbiBDb21wYXJpc29uIiwgeGxhYiA9ICJEaXN0YW5jZSBiZXR3ZWVuIENvbnNlY3V0aXZlIFBhbGluZHJvbWVzIExvY2F0aW9ucyIsIHlsaW0gPSBjKDAsMC4wMDEpKQpsaW5lcyhkZW5zaXR5KGRpc3RhbmNlLnBhaXIsIGFkanVzdCA9IDIpLCBjb2wgPSByZ2IoMSwwLDAsMC41KSkKRXhwbyA8LSByZXhwKG4tMSwgcmF0ZSA9IDEvbWVhbihkaXN0YW5jZS5wYWlyKSkKaGlzdChFeHBvLCBicmVha3MgPSAxNSwgY29sID0gcmdiKDAsMCwxLDAuNSksIHByb2JhYmlsaXR5ID0gVFJVRSwgYWRkID0gVFJVRSkKbGluZXMoZGVuc2l0eShFeHBvLCBhZGp1c3QgPSAyKSwgY29sID0gcmdiKDAsMCwxLDAuNSkpCmxlZ2VuZCh4ID0gNDIwMCwgeSA9IDAuMDAwOSwgbGVnZW5kID0gYygiU2FtcGxlIiwgIkV4cG9uZW50aWFsIiksIGx0eSA9IGMoMSwxKSwgY29sID0gYyhyZ2IoMSwwLDAsMC41KSwgcmdiKDAsMCwxLDAuNSkpKQoKIyBDaGktc3F1YXJlIEdvb2RuZXNzIG9mIEZpdCBUZXN0CiMgQ29uc3RydWN0IG9ic2VydmVkIG51bWJlcnMgb2YgaW50ZXJ2YWxzCnNwYWNpbmdzLm9ic2VydmVkIDwtIHNvcnQoZGlzdGFuY2UucGFpciwgZGVjcmVhc2luZyA9IEZBTFNFKQojIENvbnN0cnVjdCBleHBlY3RlZCBudW1iZXIgb2YgaW50ZXJ2YWxzCmxhbWJkYSA8LSAxL21lYW4oZGlzdGFuY2UucGFpcikKc3BhY2luZ3MuZXhwZWN0ZWQgPC0gcmVwKChuLTEpKmV4cCgtbGFtYmRhKSx0aW1lcyA9IG4tMSkKCmNoaV8yIDwtIHN1bSgoc3BhY2luZ3Mub2JzZXJ2ZWQgLSBzcGFjaW5ncy5leHBlY3RlZCleMi9zcGFjaW5ncy5leHBlY3RlZCkKY2hpMl9jb21wYXJlIDwtIHFjaGlzcShwID0gMC45NSwgZGYgPSBuLTMpCnBfdmFsdWUgPC0gcGNoaXNxKGNoaV8yLCBkZiA9IG4tMywgbG93ZXIudGFpbCA9IEZBTFNFKQpwX3ZhbHVlCiMjIFZpc3VhbGl6YXRpb24gb2YgdGhlIFJlc2lkdWFsClJlc2lkdWFscyA8LSAoc3BhY2luZ3Mub2JzZXJ2ZWQgLSBzcGFjaW5ncy5leHBlY3RlZCkgLyBzcXJ0KHNwYWNpbmdzLmV4cGVjdGVkKQpwbG90KFJlc2lkdWFscywgdHlwZSA9ICdoJywgeWxhYiA9ICJTdGFuZGFyZGl6ZWQgUmVzaWR1YWxzIiwgeGxhYiA9ICJQYWxpbmRyb21lIGxvY2F0aW9ucyIsIG1haW4gPSAiUGxvdCBvZiBTdGFuZGFyZGl6ZWQgUmVzaWR1YWwgZm9yIExvY2F0aW9ucyAoZGl2aWRlZCBpbiA1MDAgc3ViLWludGVydmFscykiKQoKCiMgQ29uc2VjdXRpdmUgVHJpcGxldHMKZGlzdGFuY2UudHJpcGxldHMgPC0gYWJzKGxvY2F0aW9ucy5zb3J0ZWRbLTFdWy0xXS1sb2NhdGlvbnMuc29ydGVkWy1sZW5ndGgobG9jYXRpb25zLnNvcnRlZCldWy1sZW5ndGgobG9jYXRpb25zLnNvcnRlZCkrMV0pCgojIEhpc3RvZ3JhbSBvZiBzcGFjaW5ncyBvZiBwYWxpbmRyb21lcyBpbiBvcmlnaW5hbCBkYXRhIGFuZCBleHBvbmVudGlhbCBkaXN0cmlidXRpb24KaGlzdChkaXN0YW5jZS50cmlwbGV0cywgYnJlYWtzPSAxNSwgY29sID0gcmdiKDEsMCwwLDAuNSksIHByb2JhYmlsaXR5ID0gVFJVRSwgbWFpbiA9ICJDb25zZWN1dGl2ZSBUcmlwbGV0cyBTcGFjaW5ncyBEaXN0cmlidXRpb24gQ29tcGFyaXNvbiIsIHhsYWIgPSAiRGlzdGFuY2UgYmV0d2VlbiBoaXRzIHRoYXQgYXJlIHR3byBhcGFyYXR1cyIsIHlsaW0gPSBjKDAsMC4wMDEpKQpsaW5lcyhkZW5zaXR5KGRpc3RhbmNlLnBhaXIsIGFkanVzdCA9IDIpLCBjb2wgPSByZ2IoMSwwLDAsMC41KSkKR2FtIDwtIHJnYW1tYShuLTIsIDIsIDEvbWVhbihkaXN0YW5jZS5wYWlyKSkKaGlzdChHYW0sIGJyZWFrcyA9IDE1LCBjb2wgPSByZ2IoMCwwLDEsMC41KSwgcHJvYmFiaWxpdHkgPSBUUlVFLCBhZGQgPSBUUlVFKQpsaW5lcyhkZW5zaXR5KEdhbSwgYWRqdXN0ID0gMiksIGNvbCA9IHJnYigwLDAsMSwwLjUpKQpsZWdlbmQoeCA9IDQyMDAsIHkgPSAwLjAwMDksIGxlZ2VuZCA9IGMoIlNhbXBsZSIsICJHYW1tYSIpLCBsdHkgPSBjKDEsMSksIGNvbCA9IGMocmdiKDEsMCwwLDAuNSksIHJnYigwLDAsMSwwLjUpKSkKCiMgQ2hpLXNxdWFyZSBHb29kbmVzcyBvZiBGaXQgVGVzdAojIENvbnN0cnVjdCBvYnNlcnZlZCBudW1iZXJzIG9mIGludGVydmFscwpzcGFjaW5ncy5vYnNlcnZlZCA8LSBzb3J0KGRpc3RhbmNlLnBhaXIsIGRlY3JlYXNpbmcgPSBGQUxTRSkKIyBDb25zdHJ1Y3QgZXhwZWN0ZWQgbnVtYmVyIG9mIGludGVydmFscwpsYW1iZGEgPC0gMS9tZWFuKGRpc3RhbmNlLnBhaXIpCnNwYWNpbmdzLmV4cGVjdGVkIDwtIHJlcCgobi0xKSpleHAoLWxhbWJkYSksdGltZXMgPSBuLTEpCgpjaGlfMiA8LSBzdW0oKHNwYWNpbmdzLm9ic2VydmVkIC0gc3BhY2luZ3MuZXhwZWN0ZWQpXjIvc3BhY2luZ3MuZXhwZWN0ZWQpCmNoaTJfY29tcGFyZSA8LSBxY2hpc3EocCA9IDAuOTUsIGRmID0gbi0zKQpwX3ZhbHVlIDwtIHBjaGlzcShjaGlfMiwgZGYgPSBuLTMsIGxvd2VyLnRhaWwgPSBGQUxTRSkKcF92YWx1ZQojIyBWaXN1YWxpemF0aW9uIG9mIHRoZSBSZXNpZHVhbApSZXNpZHVhbHMgPC0gKHNwYWNpbmdzLm9ic2VydmVkIC0gc3BhY2luZ3MuZXhwZWN0ZWQpIC8gc3FydChzcGFjaW5ncy5leHBlY3RlZCkKcGxvdChSZXNpZHVhbHMsIHR5cGUgPSAnaCcsIHlsYWIgPSAiU3RhbmRhcmRpemVkIFJlc2lkdWFscyIsIHhsYWIgPSAiUGFsaW5kcm9tZSBsb2NhdGlvbnMiLCBtYWluID0gIlBsb3Qgb2YgU3RhbmRhcmRpemVkIFJlc2lkdWFsIGZvciBMb2NhdGlvbnMgKGRpdmlkZWQgaW4gNTAwIHN1Yi1pbnRlcnZhbHMpIikKYGBgCgoKIyMgU2NlbmFyaW8gMzogQ291bnRzClVzZSBncmFwaGljYWwgbWV0aG9kcyBhbmQgbW9yZSBmb3JtYWwgc3RhdGlzdGljYWwgdGVzdHMgdG8gZXhhbWluZSB0aGUgY291bnRzIG9mIHBhbGluZHJvbWVzIGluIHZhcmlvdXMgcmVnaW9ucyBvZiB0aGUgRE5BLiBTcGxpdCB0aGUgRE5BIGludG8gbm9ub3ZlcmxhcHBpbmcgcmVnaW9ucyBvZiBlcXVhbCBsZW5ndGggdG8gY29tcGFyZSB0aGUgbnVtYmVyIG9mIHBhbGluZG9tcmVzIGluIGFuIGludGVydmFsIHRvIHRoZSBudW1iZXIgb2YgdGhhdCB5b3Ugd291bGQgZXhwZWN0IGZyb20gdW5pZm9ybSByYW5kb20gc2NhdHRlci4gVGhlIGNvdW50cyBmb3Igc2hvcnRlciByZWdpb25zIHdpbGwgYmUgbW9yZSB2YXJpYWJsZSB0aGFuIHRob3NlIGZvciBsb2duZXIgcmVnaW9ucy4gQWxzbywgY29uc2lkZXIgY2xhc3NpZnlpbmcgdGhlIHJlZ2lvbnMgYWNjb3JkaW5nIHRvIHRoZSBudW1iZXIgb2YgY291bnRzLgpgYGB7cn0KayA8LSA1MAp0YWIgPC0gdGFibGUoY3V0KGxvY2F0aW9ucywgYnJlYWtzID0gc2VxKDAsIE4sIGxlbmd0aC5vdXQgPSBrKzEpLCBpbmNsdWRlLmxvd2VzdCA9IFRSVUUpKQpjb3VudHMub2JzIDwtIGFzLnZlY3Rvcih0YWIpCmEgPC0gdGFibGUoY3V0KGNvdW50cy5vYnMsIGJyZWFrcyA9IHNlcShtaW4oY291bnRzLm9icyksIG1heChjb3VudHMub2JzKSwgbGVuZ3RoLm91dCA9IGsrMSksIGluY2x1ZGUubG93ZXN0ID0gVFJVRSkpCgojIEhpc3RvZ3JhbSBvZiBjb3VudHMgb2YgcGFsaW5kcm9tZXMgaW4gb3JpZ2luYWwgZGF0YSBhbmQgcG9pc3NvbiBkaXN0cmlidXRpb24KaGlzdChjb3VudHMub2JzLCBicmVha3MgPSAxNSwgY29sID0gcmdiKDEsMCwwLDAuNSksIHByb2JhYmlsaXR5ID0gVFJVRSwgbWFpbiA9ICJDb3VudHMgRGlzdHJpYnV0aW9uIENvbXBhcmlzb24gKDUwIFN1Yi1pbnRlcnZhbHMpIiwgeGxhYiA9ICJOdW1iZXIgb2YgUGFsaW5kcm9tZXMgU2l0ZXMgSW5zaWRlIGFuIEludGVydmFsIiwgeWxpbSA9IGMoMCwwLjIpKQpsaW5lcyhkZW5zaXR5KGNvdW50cy5vYnMsIGFkanVzdCA9IDIpLCBjb2wgPSByZ2IoMSwwLDAsMC41KSkKUG9pcyA8LSBycG9pcyhuLCBsYW1iZGEgPSBtZWFuKGNvdW50cy5vYnMpKQpoaXN0KFBvaXMsIGJyZWFrcyA9IDE1LCBjb2wgPSByZ2IoMCwwLDEsMC41KSwgcHJvYmFiaWxpdHkgPSBUUlVFLCBhZGQgPSBUUlVFKQpsaW5lcyhkZW5zaXR5KFBvaXMsIGFkanVzdCA9IDIpLCBjb2wgPSByZ2IoMCwwLDEsMC41KSkKbGVnZW5kKHggPSAxMiwgeSA9IDAuMTUsIGxlZ2VuZCA9IGMoInNhbXBsZSIsICJQb2lzc29uIiksIGx0eSA9IGMoMSwxKSwgY29sID0gYyhyZ2IoMSwwLDAsMC41KSwgcmdiKDAsMCwxLDAuNSkpKQoKIyBDaGktU3F1YXJlIFRlc3RpbmcKIyBDb25zdHJ1Y3QgcGFsaW5kcm9tZSBjb3VudCBudW1iZXIKcGFsaW5kcm9tZS5jb3VudCA8LSBjKCIwLDEsMiIsICIzIiwiNCIsIjUiLCI2IiwiNyIsIjgrIikKIyBDb25zdHJ1Y3Qgb2JzZXJ2ZWQgbnVtYmVyIG9mIGludGVydmFscwppbnRlcnZhbHMub2JzZXJ2ZWQgPC0gYyg4LCA5LCAxMywgMTAsIDgsIDgsIDUpIAojIENvbnN0cnVjdCBleHBlY3RlZCBudW1iZXIgb2YgaW50ZXJ2YWxzCmV4cGVjdGVkIDwtIGMoKQpsYW1iZGEgPC0gbi9rCmZvciAoaSBpbiBjKDA6MTcpKXsKICBleHBlY3QgPC0gayogZXhwKC1sYW1iZGEpKiBsYW1iZGEqKmkgL2ZhY3RvcmlhbChpKQogIGV4cGVjdGVkIDwtIGMoZXhwZWN0ZWQsIGV4cGVjdCkKfQpzdW0gPC0gMApmb3IgKGogaW4gYyg5OjE3KSl7CiAgc3VtIDwtIHN1bStleHBlY3RlZFtqXQp9CmludGVydmFscy5leHBlY3RlZCA8LSBjKGV4cGVjdGVkWzFdK2V4cGVjdGVkWzJdK2V4cGVjdGVkWzNdLGV4cGVjdGVkWzRdLGV4cGVjdGVkWzVdLGV4cGVjdGVkWzZdLGV4cGVjdGVkWzddLGV4cGVjdGVkWzhdLHN1bSkKCiMgQ3JlYXRlIGNvbnRpbmdlbmN5IHRhYmxlCmIgPC0gZGF0YS5mcmFtZShwYWxpbmRyb21lLmNvdW50LGludGVydmFscy5vYnNlcnZlZCxpbnRlcnZhbHMuZXhwZWN0ZWQpCmIKCmNoaV8yIDwtIHN1bSgoaW50ZXJ2YWxzLm9ic2VydmVkIC0gaW50ZXJ2YWxzLmV4cGVjdGVkKV4yL2ludGVydmFscy5leHBlY3RlZCkKY2hpMl9jb21wYXJlIDwtIHFjaGlzcShwID0gMC45NSwgZGYgPSA3KQpwX3ZhbHVlIDwtIHBjaGlzcShjaGlfMiwgZGYgPSA3LCBsb3dlci50YWlsID0gRkFMU0UpCnByaW50KGNhdCgiXG5XaGVuIGNvbmR1Y3RpbmcgY2hpX3NxdWFyZSBHb29kbmVzcyBvZiBmaXQgdGVzdCBjb21wYXJpbmcgbG9jYXRpb25zKGRpdmlkZWQgaW4gNTAwIHN1Yi1pbnRlcnZhbHMpIGFnYWluc3QgdW5pZm9ybSBkaXN0cmlidXRpb25cbiIpKQpwcmludChwYXN0ZSgiVGhlIHZhbHVlIG9mIGNoaV9zcXVhcmUgc3RhdGlzdGljIGlzIiwgY2hpXzIpKQpwcmludChwYXN0ZSgiVGhlIHBfdmFsdWUgaXMiLCBwX3ZhbHVlKSkKCmBgYAoKCiMjIFNjZW5hcmlvIDQ6IFRoZSBCaWdnZXN0IENsdXN0ZXIKRG9lcyB0aGUgaW50ZXJ2YWwgd2l0aCB0aGUgZ3JlYXRlc3QgbnVtYmVyIG9mIHBhbGluZHJvbWVzIGluZGljYXRlIGEgcG90ZW50aWFsIG9yaWdpbiBvZiByZXBsaWNhdGlvbj8gQmUgY2FyZWZ1bCBpbiBtYWtpbmcgeW91ciBpbnRlcnZhbHMsIGZvciBhbnkgc21hbGwsIGJ1dCBzaWduaWZpY2FudCBkZXZpYXRpb25zIGZyb20gcmFuZG9tIHNjYXR0ZXIsIHN1Y2ggYXMgYSB0aWdodCBjbHVzdGVyIG9mIGEgZmV3IHBhbGluZHJvbWVzLCBjb3VsZCBlYXNpbHkgZ28gdW5kZXRlY3RlZCBpZiB0aGUgcmVnaW9ucyBleGFtaW5lZCBhcmUgdG9vIGxhcmdlLiBBbHNvLCBpZiB0aGUgcmVnaW9ucyBhcmUgdG9vIHNtYWxsLCBhIGNsdXN0ZXIgb2YgcGFsaW5kcm9tZXMgbWF5IGJlIHNwbGl0IGJldHdlZW4gYWRqYWNlbnQgaW50ZXJhdmxzIGFuZCBub3QgYXBwZWFyIGFzIGEgaGlnaC1jb3VudCBpbnRlcnZhbC4KYGBge3J9CmZpbmFsIDwtIGFycmF5KGRpbT1jKDUwMCwxKSkKaW50ZXJ2YWxfbGVuZ3RoIDwtIGFycmF5KGRpbT1jKDUwMCwxKSkKbGFtZGEgPC0gYXJyYXkoZGltPWMoNTAwLDEpKQpmb3IgKGsgaW4gNTA6NTAwKXsKICB0YWIgPC0gdGFibGUoY3V0KGxvY2F0aW9ucywgYnJlYWtzID0gc2VxKDAsIE4sIGxlbmd0aC5vdXQgPSBrKzEpLCBpbmNsdWRlLmxvd2VzdCA9IFRSVUUpKQogIGhlYWQodGFiLDEwKQogIHRhYjwtYXMudmVjdG9yKHRhYikKICBsYW1kYVtrLF0gPC1zdW0odGFiKS9rCiAgdGhyZXNob2xkIDwtbWF4KHRhYikKICByZXN1bHQgPC0gMAogIGludGVydmFsX2xlbmd0aFtrLF0gPC0gTi9rCiAgZm9yIChpIGluIDA6KHRocmVzaG9sZC0xKSl7CiAgICByZXN1bHQgPC0gcmVzdWx0KygobGFtZGFba11eaSkqZXhwKC1sYW1kYVtrXSkvZmFjdG9yaWFsKGkpKQogIH0KICBmaW5hbFtrLF0gPC0gMS1yZXN1bHReawp9CnJlc3VsdCA8LSBkYXRhLmZyYW1lKGxhbWRhLGludGVydmFsX2xlbmd0aCxmaW5hbCkKCiMgRGlzcGxheSBUYWJsZSBjb250YWluaW5nIHRoZSBwcm9iYWJpbGl0eSBvZiBhIFBvaXNzb24gRGlzdHJpYnV0aW9uIGhhdmluZyBlIGdyZWF0ZXN0IG51bWJlciBvZiBoaXRzIGF0IGxlYXN0IGsgZm9yIGVhY2ggc3ViLWludGVydmFsIGRpdmlzaW9ucwpyZXN1bHRbYyg1MCwxMDAsNTAwKSxdCmBgYAoKCiMjIEFkZGl0aW9uYWwgU2NlbmFyaW86IFRlc3RpbmcgaWYgSElWIFRlc3RpbmcgcG9zaXRpdmUgaXMgcmVsYXRlZCB0byBhZ2UKVE9ETyBEZXNjcmlwdGlvbgpgYGB7cn0KIyBDbGVhbiBvdXQgJ3Vua25vd24nIGRhdGEgYW5kIGNvbnZlcnQgZmFjdG9yIHRvIG51bWVyaWNhbCB2YWx1ZXMKaGVhbHRoIDwtIHRyYW5zZm9ybShoZWFsdGgsIGFnZV95cnMgPSBhcy5udW1lcmljKGFnZV95cnMpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgaGl2ID0gYXMuY2hhcmFjdGVyKGhpdikpCmhlYWx0aC5pbmQgPC0gd2hpY2goaGVhbHRoJGhpdiAhPSAidW5rbm93biIpCmhlYWx0aCA8LSBoZWFsdGhbaGVhbHRoLmluZCxdCgojIFRvdGFsIG51bWJlciBvZiBwZW9wbGUgdGhhdCBoYXZlIGhpdgpwb3B1bGF0aW9uID0gbnJvdyhoZWFsdGgpCnBvcF9oaXYgPC0gbnJvdyhoZWFsdGhbd2hpY2goaGVhbHRoJGhpdj09J3Bvc2l0aXZlJyksXSkKCiMgU3BsaXQgdGhlIGFnZSBpbnRvIGZvdXIgZ3JvdXBzCiMgMC0yMAphZ2VfZmlyc3QgPC0gaGVhbHRoJGFnZV95cnNbd2hpY2goaGVhbHRoJGFnZV95cnM8MjEpXQphZ2VfcHJvcG9ydGlvbl9maXJzdCA8LSBsZW5ndGgoYWdlX2ZpcnN0KS9wb3B1bGF0aW9uCmhpdl9wcm9wb3J0aW9uX2ZpcnN0PC0gbnJvdyhoZWFsdGhbd2hpY2goKGhlYWx0aCRoaXY9PSAicG9zaXRpdmUiKSAmIChoZWFsdGgkYWdlX3lycyA8MjEpKSxdKS9wb3BfaGl2CgojIDIxLTQwCmFnZV9zZWNvbmQ8LWhlYWx0aCRhZ2VfeXJzW3doaWNoKGhlYWx0aCRhZ2VfeXJzPjIwICYgaGVhbHRoWydhZ2VfeXJzJ108NDEpXQphZ2VfcHJvcG9ydGlvbl9zZWNvbmQgPC0gbGVuZ3RoKGFnZV9zZWNvbmQpL3BvcHVsYXRpb24KaGl2X3Byb3BvcnRpb25fc2Vjb25kPC1ucm93KGhlYWx0aFt3aGljaChoZWFsdGgkYWdlX3lycz4yMCAmaGVhbHRoJGFnZV95cnM8NDEgJiBoZWFsdGgkaGl2PT0icG9zaXRpdmUiKSxdKS9wb3BfaGl2CgojIDQxLTYwCmFnZV90aGlyZDwtaGVhbHRoJGFnZV95cnNbd2hpY2goaGVhbHRoWydhZ2VfeXJzJ10+NDAgJiBoZWFsdGhbJ2FnZV95cnMnXTw2MSldCmFnZV9wcm9wb3J0aW9uX3RoaXJkIDwtIGxlbmd0aChhZ2VfdGhpcmQpL3BvcHVsYXRpb24KaGl2X3Byb3BvcnRpb25fdGhpcmQ8LW5yb3coaGVhbHRoW3doaWNoKGhlYWx0aCRhZ2VfeXJzPjQwICYgaGVhbHRoJGFnZV95cnM8NjEgJmhlYWx0aCRoaXY9PSJwb3NpdGl2ZSIpLF0pL3BvcF9oaXYKCiMgNjErCmFnZV9sYXN0PC1oZWFsdGgkYWdlX3lyc1t3aGljaChoZWFsdGhbJ2FnZV95cnMnXT42MCldCmFnZV9wcm9wb3J0aW9uX2xhc3QgPC0gbGVuZ3RoKGFnZV9sYXN0KS9wb3B1bGF0aW9uCmhpdl9wcm9wb3J0aW9uX2xhc3Q8LW5yb3coaGVhbHRoW3doaWNoKGhlYWx0aCRhZ2VfeXJzPjYwICYgaGVhbHRoJGhpdj09InBvc2l0aXZlIiksXSkvcG9wX2hpdgoKIyBFeHBlY3RlZCBEYXRhCnBvcHVsYXRpb25fZGlzdCA8LWMoYWdlX3Byb3BvcnRpb25fZmlyc3QsYWdlX3Byb3BvcnRpb25fc2Vjb25kLGFnZV9wcm9wb3J0aW9uX3RoaXJkLGFnZV9wcm9wb3J0aW9uX2xhc3QpCiMgT2JzZXJ2ZWQgRGF0YQpoaXZfZGlzdDwtYyhoaXZfcHJvcG9ydGlvbl9maXJzdCxoaXZfcHJvcG9ydGlvbl9zZWNvbmQsaGl2X3Byb3BvcnRpb25fdGhpcmQsaGl2X3Byb3BvcnRpb25fbGFzdCkKCiMgR29vZG5lc3MtZml0dGVzdApjaGlfMiA8LSBzdW0oKGhpdl9kaXN0IC0gcG9wdWxhdGlvbl9kaXN0KV4yL3BvcHVsYXRpb25fZGlzdCkKY2hpMl9jb21wYXJlIDwtIHFjaGlzcShwID0gMC45NSwgZGYgPSAzKQpwX3ZhbHVlIDwtIHBjaGlzcShjaGlfMiwgZGYgPSAzLCBsb3dlci50YWlsID0gRkFMU0UpCnByaW50KHBhc3RlKCJUaGUgcF92YWx1ZSBvZiBHb29kbmVzcyBvZiBGaXQgVGVzdCBpcyIscF92YWx1ZSkpCgojVmlzdWFsaXphdGlvbgpSZXNpZHVhbHMgPC0gKGhpdl9kaXN0IC0gcG9wdWxhdGlvbl9kaXN0KSAvIHNxcnQocG9wdWxhdGlvbl9kaXN0KQpwbG90KFJlc2lkdWFscywgdHlwZSA9ICdoJywgeWxhYiA9ICJTdGFuZGFyZGl6ZWQgUmVzaWR1YWxzIiwgeGxhYiA9ICJQcm9wb3J0aW9uIG9mIFBvc2l0aXZlIEhJViIsIG1haW4gPSAiUGxvdCBvZiBTdGFuZGFyZGl6ZWQgUmVzaWR1YWwgZm9yIEFnZSBhbmQgSElWIFBvc2l0aXZlIikKYGBgCgoKTnVsbCBIeXBvdGhlc2lzOiBUaGUgcHJvcG9ydGlvbiBvZiBhZ2UgaW4gdGhlIHBvcHVsYXRpb24gaXMgdW5yZWxhdGVkIHdpdGggdGhlIHByb3BvcnRpb24gb2YgcGVvcGxlIGhhdmluZyBoaXYuKEFnZSBpcyBub3QgYW4gaW5mbHVlbmNpbmcgZmFjdG9yIGZvciBISVYgdGVzdGluZyBwb3NpdGl2ZSkKU2luY2UgcC12YWx1ZSBvZiB0aGlzIGNoaS1zcXVhcmUgZ29vZG5lc3Mgb2YgZml0IHRlc3QgaXMgY2xvc2UgdG8gMSwgd2Ugc2VlIHRoYXQgZGV2aWF0aW9ucyBhcyBsYXJnZSBhcyBvdXJzIChvciBsYXJnZXIpIGFyZSB2ZXJ5IGxpa2VseS4gSW4gYWRkaXRpb24sIGhhdmluZyB2YWx1ZXMgb2YgdGhlIHN0YW5kYXJkaXplZCByZXNpZHVhbCBsZXNzIHRoYW4gMyBzdWdnZXN0cyB0aGF0IGl0IGlzIGEgZ29vZCBmaXQgb2YgdGhlIGFnZSBkaXN0cmlidXRpb24gdG8gZXN0aW1hdGUgdGhlIHBlb3BsZSB0ZXN0aW5nIHBvc2l0aXZlIG9uIGhpdi4gSGVuY2UsIHdlIHJlamVjdCB0aGUgbnVsbCBoeXBvdGhlc2lzIGFuZCBjb25jbHVkZSB0aGF0IHRoZSBkaXN0cmlidXRpb24gb2YgcHJvcG9ydGlvbiBvZiBhZ2UgbWF0Y2hlcyB3aXRoIHRoZSB0aGUgZGlzdHJpYnV0aW9uIG9mIHBlb3BsZSB0ZXN0aW5nIHBvc2l0aXZlIG9uIEhJVi4KCg==